2130. 链表最大孪生和

在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。
比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。
孪生和 定义为一个节点和它孪生节点两者值之和。
给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。

 



找中间结点，逆置链表
struct ListNode* findmid(struct ListNode*head)
{
    if(head==NULL)
    {
        return NULL;
    }
    struct ListNode*fast=head,*slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}

struct ListNode*revarse(struct ListNode*head)
{
    if(head==NULL)
    {
        return NULL;
    }
    struct ListNode*n1=NULL;
    struct ListNode*n2=head;
    struct ListNode*n3=n2->next;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
        {
            n3=n3->next;
        }
    }
    return n1;
}

int pairSum(struct ListNode* head)
{
    struct ListNode*cur=head;
    struct ListNode*mid=findmid(head);
    struct ListNode*rhead=revarse(mid);
    int max=0;
    while(rhead)
    {
        if((cur->val+rhead->val)>max)
        {
            max=cur->val+rhead->val;
        }
        cur=cur->next;
        rhead=rhead->next;
    }
    return max;
}




class Solution {
public:
    int pairSum(ListNode* head) {
        ListNode *fast = head->next, *slow = head, *p = nullptr;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        fast = slow->next;
        slow->next = nullptr;
        while (fast) {  // 将后半部分逆置(头插法)
            p = fast->next;
            fast->next = slow->next;
            slow->next = fast;
            fast = p;
        }
        fast = slow->next;    // fast指向后半部分开始
        int maxSum = 0;
        while (fast) { 
            maxSum = max(maxSum, head->val + fast->val);
            fast = fast->next;
            head = head->next;
        }
        return maxSum;
    }
};

